package lc20240701;

//给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
//计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
//你可以认为每种硬币的数量是无限的。

import java.util.Arrays;

public class CoinConversion {
    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 11;
        CoinConversion coinConversion = new CoinConversion();
        System.out.println(coinConversion.coinChange(coins, amount));
    }

    public int coinChange(int[] coins, int amount) {
        //如果总金额为 0，则不需要任何硬币
        if (amount < 1) return 0;
        //dp[i] 表示凑成金额 i 所需的最少硬币数
        int[] dp = new int[amount + 1];
        //将 dp 数组初始化为一个较大的值 amount + 1，这样可以确保任何合法结果都比它小.
        Arrays.fill(dp, amount + 1);
        //凑成金额 0 需要 0 枚硬币
        dp[0] = 0;
        //从 1 到 amount 逐一计算最少硬币数
        for (int i = 1; i <= amount; i++) {
            // 遍历每一种硬币面额
            for (int coin : coins) {
                // 如果当前金额 i 大于等于硬币面额 coin
                if (i - coin >= 0) {
                    // 更新 dp[i]，取 dp[i] 和 dp[i - coin] + 1 的较小值
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        // 如果 dp[amount] 仍然是初始值 amount + 1，说明无法凑成总金额，返回 -1
        return dp[amount] > amount ? -1 : dp[amount];
    }
    /*
    初始化：
    int[] dp = new int[amount + 1];：创建一个长度为 amount + 1 的数组 dp。
    Arrays.fill(dp, amount + 1);：将 dp 数组中的所有元素初始化为 amount + 1，一个不可能的高值。
    dp[0] = 0;：凑成金额为 0 需要 0 枚硬币。
    动态规划填表：
    for (int i = 1; i <= amount; i++)：遍历从 1 到 amount 的每一个值 i。
    for (int coin : coins)：遍历每一种硬币面额 coin。
    if (i - coin >= 0)：如果当前金额 i 大于等于硬币面额 coin。
    dp[i] = Math.min(dp[i], dp[i - coin] + 1);：更新 dp[i]，取 dp[i] 和 dp[i - coin] + 1 的较小值。
    结果判断：
    return dp[amount] > amount ? -1 : dp[amount];：如果 dp[amount] 仍然是 amount + 1，说明没有任何一种硬币组合能组成总金额，返回 -1。否则，返回 dp[amount] 的值。
     */
}
